package lc.二叉树;

import utils.TreeNode;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/10/11
 */
public class Math_110平衡二叉树 {

    public boolean isBalanced(TreeNode root) {

       return check(root) != -1;

    }

    private int check(TreeNode root) {

        if (root == null) {
            return 0;
        }
        int left = check(root.left);
        if (left == -1) {
            return -1;
        }
        int right = check(root.right);
        if (right == -1) {
            return -1;
        }
        if (Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left,right) + 1;
    }

    public boolean isBalanced1(TreeNode root) {

        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left),depth(root.right)) + 1;
    }

}
